/*
 * @Description: 
 * @version: 
 * @Author: cy
 * @Date: 2022-05-05 15:20:03
 * @LastEditors: cy
 * @LastEditTime: 2022-05-05 16:54:28
 */
// LeetCode 20:有效的括号,用字典来优化之前的算法，之前用栈的方式实现
// var isValid = function(s) { 
//     if (s.length % 2 === 1) {
//         return false;
//     }
//     const stack = [];
//     for (let i = 0; i < s.length; i += 1) {
//         const c = s[i];
//         if (c === '(' || c === '{' || c === '{') {
//             stack.push(c);
//         } else {
//             const t = stack[stack.length - 1];
//             if (
//                 (t === '(' && c === ')') ||
//                 (t === '{' && c === '}') ||
//                 (t === '{' && c === ']')
//             ) {
//                 stack.pop();
//             } else {
//                 return false;
//             }
//         }
//     }
//     return stack.length === 0;
// }，修改一下
var isValid = function(s) { 
    if (s.length % 2 === 1) {
        return false;
    }
    const stack = [];
    // Map的空间复杂度是O(1)，它不会随着某个变量的增加而增加，
    // O(1)的复杂度不会改变我们的复杂度，这里的整体复杂度仍然是O(n)
    const map = new Map();
    map.set('(', ')');
    map.set('{', '}');
    map.set('[', ']');
    for (let i = 0; i < s.length; i += 1) {
        const c = s[i];
        if (map.has(c)) {
            stack.push(c);
        } else {
            const t = stack[stack.length - 1];
            if (map.get(t) === c) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
}
